package zuo.highLevel_5;

/**
 * @Author: Forx
 * @Data: 2021/7/8
 * @Desc: Algorithm - zuo.highLevel_5
 * @Version: v1.0
 */


import java.util.Arrays;
import java.util.Stack;

/**
 * 一个char类型的数组chs,其中所有的字符都不同。
 * 例如，chs=['A','B','C',...'Z'],则字符串与整数的对应关系如下：
 * A . B . . Z , AA , AB . . . AZ , BA , BB . . ZZ , AAA . . ZZZ , AAAA . .
 * 1,2,26,       27,28...52,        53,54...702,     703...18278,18279...
 * 例如，chs=['A','B','C'],则字符串与整数的对应关系如下：
 * A , B , C , AA , AB . . CC , AAA . . . CCC , AAAA . .
 * 1,  2,  3,  4,    5...   12,  13...       39,   40...
 * 给定一个数组chs,实现根据对应关系完成字符串与整数相互转换的两个函数。
 * [A...Z]
 *  AA 26*1 + 1
 *  AZ 26*1 + 26
 *  BA 26*2+1
 *  ...
 *  ZZ 26*26+26  = 702 = 26*27;
 *
 *  AAA 26*27 + 1 = 703   (AA A 中的AA是27)
 *  AAAA 26*703+1 = 18279  (AAA A)
 *
 * [A...C]
 * A 1 B 2
 * AA 3*1+1 = 4
 * CC 3*3 + 3 = 12
 * AAA 3*4+1 = 13
 * AAAA 3*13+1 = 40
 * */
class charBuffTransform{
    private char[] chars;
    public charBuffTransform() {
        chars = null;
    }

    public charBuffTransform(char[] chars) {
        this.chars = chars;
    }
    public int  transform(char[] in,int left,int right){
        if(left==right){
            for (int i = 0; i < chars.length; i++) {
                if(in[left] == chars[i]){
                    return i+1;
                }
            }
        }
        int base = transform(in,left,right-1) * chars.length;
        for (int i = 0; i < chars.length; i++) {
            if(in[right]==chars[i]){
                base+=i+1;
                break;
            }
        }
        return base;
    }
    //error
    public String transformToChars(int num){
        if(num <= chars.length){

            return String.valueOf(chars[num-1]);
        }
        int mi = 1;
        int base = chars.length;
        while (base <= num){
            base+=Math.pow(chars.length,++mi);
        }
        mi--;
        base = (int)Math.pow(chars.length,mi);
        mi=0;
        int index = num;

        while (index > chars.length){
            base/=chars.length;
            index  = index%(base);
        }

        return String.valueOf(chars[index-1]) + transformToChars(num-base);


    }

    public void tets(){
        chars = new char[]{'A','B','C'};
        System.out.println(transform(new char[]{'C', 'C', 'C', 'A'}, 0, 2));
        System.out.println(transformToChars(13));

    }

}
/**
 * 给定一个二维数组matrix,每个单元都是一个整数，有正有负。最开始的时候小Q操纵
 * 一条长度为0的蛇蛇从矩阵最左侧任选一个单元格进入地图，蛇每次只能够到达当前位
 * 置的右上相邻，右侧相邻和右下相邻的单元格。蛇蛇到达一个单元格后，自身的长度会
 * 瞬间加上该单元格的数值，任何情况下长度为负则游戏结束。小Q是个天才，他拥有一
 * 个超能力，可以在游戏开始的时候把地图中的某一个节点的值变为其相反数（注：最多
 * 只能改变一个节点）。问在小Q游戏过程中，他的蛇蛇最长长度可以到多少？
 * 比如：
 * 1 -4 10
 * 3 -2 -1
 * 2 -1 0
 * 0 5 -2
 * 最优路径为从最左侧的3开始，3->-4(利用能力变成4)->10。所以返回17。
 * 遍历每一条路径的时候保存绝对值最大的负数,然后翻转
 *
 *
 *
 * */
class Snake{

    class Point{
        public int x;
        public int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object obj) {
            Point sec = (Point)obj;
            return x==sec.x && y==sec.y ;
        }

        @Override
        public String toString() {
            return "x: "+x + " y: " + y;
        }
    }
    public int getMaxScore(int[][] grid){
        int tempMaxScore = Integer.MIN_VALUE;
        for (int i = 0; i < grid.length; i++) {
            int temp = process(grid,new Point(0,i),0,0,1);
            if(temp>tempMaxScore){
                tempMaxScore = temp;
            }
        }
        return tempMaxScore;
    }

    class Info{
        public int noPower;
        public int withPower;

        public Info() {
        }
        public Info(int noPower, int withPower) {
            this.noPower = noPower;
            this.withPower = withPower;
        }
    }


    public int getMaxScore2(int[][] grid){
        int tempMaxScore = Integer.MIN_VALUE;
        Info[][] dp = new Info[grid.length][grid[0].length];
        for(Info[] row : dp){
           for(Info elm : row){
               elm = new Info(Integer.MIN_VALUE,Integer.MIN_VALUE);
           }
        }
        for (int i = 0; i < grid.length; i++) {
            int temp = process2(grid,new Point(0,i),0,0,1,dp);
            if(temp>tempMaxScore){
                tempMaxScore = temp;
            }
        }
        return tempMaxScore;
    }
    private int process(int[][] grid,Point start,int curLen,int curMaxNeg,int power){
//        if(start.x==grid[0].length-1)return grid[start.y][start.x];
        if(isOverGrid(grid,start)){
            return Integer.MIN_VALUE;
        }
        if(curLen < 0){
            if(power==0){
                return Integer.MIN_VALUE;
            }else {
                power=0;
                curLen -= curMaxNeg*2;
            }
        }
        if(start.x == grid[0].length-1){
            if(grid[start.y][start.x] <0){
                if(power==0){
                    return curLen;
                }else {
                    curMaxNeg = Math.min(grid[start.y][start.x],curMaxNeg);

                    return curLen+grid[start.y][start.x] - curMaxNeg*2;
                }
            }else {
                return curLen +grid[start.y][start.x];
            }
        }
        int rightUP = process(grid,new Point(start.x+1,start.y-1),curLen+grid[start.y][start.x],
                Math.min(curMaxNeg,grid[start.y][start.x])
                ,power);
        int right = process(grid,new Point(start.x+1,start.y),curLen+grid[start.y][start.x],
                Math.min(curMaxNeg,grid[start.y][start.x])
                ,power);
        int rightDOWN = process(grid,new Point(start.x+1,start.y+1),curLen+grid[start.y][start.x],
                Math.min(curMaxNeg,grid[start.y][start.x])
                ,power);
        int maxScore = Math.max(Math.max(rightUP,right),rightDOWN);
        if(maxScore == Integer.MIN_VALUE)return curLen;
        return maxScore;
    }
    //建立dp表优化
    //优化不了,因为用了路径上最大负数的概念,导致每个点在存在能力的时候所走的最大值不一样
    private int process2(int[][] grid,Point start,int curLen,int curMaxNeg,int power,Info[][] dp){
        return -1;
//        if(start.x==grid[0].length-1)return grid[start.y][start.x];
//        if(isOverGrid(grid,start)){
//            return Integer.MIN_VALUE;
//        }
//        if(curLen < 0){
//            if(power==0){
//                return Integer.MIN_VALUE;
//            }else {
//                power=0;
//                curLen -= curMaxNeg*2;
//                if(dp[start.y][start.x].noPower!=Integer.MIN_VALUE){
//                    return curLen+dp[start.y][start.x].noPower;
//                }
//            }
//        }
//        if(start.x == grid[0].length-1){
//            if(grid[start.y][start.x] <0){
//                if(power==0){
//                    dp[start.y][start.x].noPower = 0;
//                    return curLen;
//                }else {
//                    curMaxNeg = Math.min(grid[start.y][start.x],curMaxNeg);
//                    dp[start.y][start.x].noPower = curLen+grid[start.y][start.x] - curMaxNeg*2;
//                    return curLen+grid[start.y][start.x] - curMaxNeg*2;
//                }
//            }else {
//                dp[start.y][start.x].noPower = curLen +grid[start.y][start.x];
//                dp[start.y][start.x].withPower = curLen +grid[start.y][start.x];
//                return curLen +grid[start.y][start.x];
//            }
//        }
//        int noPower = Integer.MIN_VALUE;
//        int withPower = Integer.MIN_VALUE;
//        if(power==0 && dp[start.y][start.x].noPower!=Integer.MIN_VALUE ){
//            noPower = curLen+dp[start.y][start.x].noPower;
//            return noPower;
//        }
//        if(power==1 && dp[start.y][start.x].withPower!=Integer.MIN_VALUE){
//            withPower = dp[start.y][start.x].withPower + curLen;
//            return withPower;
//        }
//        int rightUP = process2(grid,new Point(start.x+1,start.y-1),curLen+grid[start.y][start.x],
//                Math.min(curMaxNeg,grid[start.y][start.x])
//                ,power,dp);
//        int right = process2(grid,new Point(start.x+1,start.y),curLen+grid[start.y][start.x],
//                Math.min(curMaxNeg,grid[start.y][start.x])
//                ,power,dp);
//        int rightDOWN = process2(grid,new Point(start.x+1,start.y+1),curLen+grid[start.y][start.x],
//                Math.min(curMaxNeg,grid[start.y][start.x])
//                ,power,dp);
//        int maxScore = Math.max(Math.max(rightUP,right),rightDOWN);
//
//        if(maxScore == Integer.MIN_VALUE){
//            return Integer.MIN_VALUE;
//        };
//        if(power==1){
//            dp[start.y][start.x].withPower = maxScore-curLen;
//        }
//        if(power==0){
//            dp[start.y][start.x].noPower = maxScore-curLen;
//        }
//        return maxScore;

    }
    private boolean isOverGrid(int[][] grid,Point point){
        return (point.x < 0 || point.y <0 || point.x >= grid[0].length || point.y >= grid.length);
    }
    public void test(){
        int[][] grid = new int[][]{
                {1,-4,10},
                {3,-2,-100},
                {2,-1,0},
                {0,5,-2000},
//                {-100,-1000,-1000000},
//                {-200,-2000,-2000000},
//                {-300,-3000,-3000000},

        };
        System.out.println(getMaxScore(grid));
    }

}

/**
 * 给定一个字符串str,str表示一个公式，公式里可能有整数、加减乘除符号和左右
 * 括号，返回公式的计算结果。
 * 【举例】
 * str="48*((70-65)-43)+8*1",返回-1816。
 * str="3+1*4",返回7。
 * str="3+(1*4)",返回7。
 * 【说明】
 * 1.可以认为给定的字符串一定是正确的公式，即不需要对str做公式有效性检查。
 * 2.如果是负数，就需要用括号括起来，比如"4*(-3)"。但如果负数作为公式的开头
 * 或括号部分的开头，则可以没有括号，比如”-3*4"和"(-3*4)"都是合法的。
 * 3.不用考虑计算过程中会发生溢出的情况。
 *  [麻烦方法]
 * 找负数,负号前加0,
 * 首先看第一个字符是不是-,如果是就加0
 * 再看(-这个字符串,如果有就在前面加0
 * 运算符栈和操作数栈
 * 如果在运算符栈中发现连续的
 *
 *
 *
 * */
class Calculate{
        private String addZero(String string){
            if(string.charAt(0)=='-'){
                string = '0'+string;
            }
            string=string.replace("(-","(0-");
            return string;
        }

        public int getValue(String string){
            Stack<Integer> numsStack = new Stack<>();
            Stack<Character> opStack = new Stack<>();

            //into stack 太麻烦
            for (int i = 0; i < string.length(); i++) {
                char c =string.charAt(i);
                if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'){
                    if(opStack.isEmpty() || c=='('){
                        opStack.push(c);
                    }else {

                    }
                }else {
                    numsStack.push(c-'0');
                }
            }


            return 0;
        }

        public int getValueEasy(String s){
            return 0;
        }
        private int[] process(char[] chars,int start){
            Stack<String> stack = new Stack<>();
            int index = 0;
            for ( index = start;  index < chars.length && chars[index]!=')'; index++) {
                String num = null;
                String op = null;
                if(chars[index]!='('){
                    if(chars[index]>='0' && chars[index] <='9'){
                        int len =1;
                        while ( index+len < chars.length &&chars[index+len]>='0' && chars[index+len] <='9'){
                            len++;
                        }
                         num =new String(chars,index,len);
                        index = index+len-1;
                    }else {
                         op = new String(chars,index,1);
                    }

                }else {
                    int[] ans = process(chars,index+1);
                    if(ans.length==2){
                        num = String.valueOf(ans[0]);
                        index = ans[1];//)出现的位置,后面会加一所以会自动调到)后面
                    }
                }
                if(stack.size()>=2){
                    if(num!=null && stack.peek().equals("*")){
                        stack.pop();//废弃栈顶的乘法操作符
                        String numTemp = stack.pop();
                        num = String.valueOf(Integer.parseInt(num) * Integer.parseInt(numTemp));
                        //stack.push(String.valueOf(Integer.parseInt(num) * Integer.parseInt(numTemp)));
                    }else if(stack.peek().equals("/")){
                        stack.pop();//废弃栈顶的除法操作符
                        String numTemp = stack.pop();
                        num = String.valueOf(Integer.parseInt(num) / Integer.parseInt(numTemp));
                        //stack.push(String.valueOf(Integer.parseInt(num) / Integer.parseInt(numTemp)));
                    }
                }
                if(num!=null){
                    stack.push(num);
                }
                if(op!=null){
                    stack.push(op);
                }
            }
            Stack<String> inverseStack = new Stack<>();
            while (!stack.isEmpty()){
                inverseStack.push(stack.pop());
            }
            while (inverseStack.size()>1){
                String num1 = inverseStack.pop();
                String op = inverseStack.pop();
                String num2 = inverseStack.pop();
                String ans;
                if(op.equals("-")){
                    ans = String.valueOf(Integer.parseInt(num1) - Integer.parseInt(num2));
                }else {
                    ans = String.valueOf(Integer.parseInt(num2) + Integer.parseInt(num1));
                }
                inverseStack.push(ans);
            }
            return new int[]{Integer.parseInt(inverseStack.pop()),index};
        }



        public void test(){
//            String str = "-3*4+(-3*4)-(4*(-3))";
//            str = addZero(str);
//            System.out.println("str = " + str);
            String exp = "-4+12+3*(4-1)+2*(5-3)*(-4)";
            exp = addZero(exp);
            int ans =  process(exp.toCharArray(),0)[0];
            System.out.println(ans);
        }
}


/**
 *请注意区分子串和子序列的不同，给定两个字符串str1和str2,求两个字符串的最长公
 * 共子串。
 * 动态规划空间压缩的技巧讲解
 *       str1[0] str1[1] str1[2] str1[3]
 *  str2[0]
 *  str2[1]
 *  str2[2]
 *  str2[3]
 *  懂了吧
 * */
class maxSameSubStrLen{

    public int getLen(String string1,String string2){
        return process2(string1.toCharArray(),string2.toCharArray());
    }
    private int process2(char[] src1,char[] src2){
        int[] dp = new int[src1.length];
        int topLeft  = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < dp.length; i++) {
            dp[i] = (src1[i] == src2[0] ? 1:0);
        }

        for (int j = 1; j < src2.length; j++) {
            for (int i = 0; i < src1.length; i++) {
                if(i == 0){
                    topLeft = dp[0];
                    dp[i] = (src2[j] == src1[i] ? 1:0);
                }else {
                    int temp =  dp[i];
                    dp[i] = (src2[j] == src1[i])?Math.max(topLeft,Math.max(dp[i-1],dp[i])) +  1:0;
                    if(dp[i] > max){
                        max = dp[i];
                    }
                    topLeft = temp;
                }
            }
        }
        return max;

    }


}
/**
 *请注意区分子串和子序列的不同，给定两个字符串str1和str2,求两个字符串的最长公
 * 共子序列。
 * 动态规划空间压缩的技巧讲解
 *          str1[0] str1[1] str1[2] str1[3]
 *  str2[0]
 *  str2[1]
 *  str2[2]
 *  str2[3]
 *  懂了吧
 * */
class maxSameSeqStrLen{

    public int getLen(String string1,String string2){
        int[][] dp = new  int[string2.length()][string1.length()];

//        return process(string1.toCharArray(),string2.toCharArray(),dp);
        return process2(string1.toCharArray(),string2.toCharArray());
    }
    private int process(char[] src1,char[] src2,int[][] dp){
        //src1-->
        //src2 |
        for (int i = 0; i <dp[0].length ; i++) {
            if(src1[i] == src2[0]){
                dp[0][i] = 1;
            }else {
                dp[0][i] = 0;
            }
        }
        for (int i = 0; i < dp.length; i++) {
            if(src2[i] == src1[0]){
                dp[i][0] = 1;
            }else {
                dp[i][0] = 0;
            }
        }

        for (int row = 1; row < dp.length; row++) {
            for (int col = 1; col < dp[0].length; col++) {
                int temp = Math.max(dp[row-1][col],Math.max( dp[row][col-1],dp[row-1][col-1])) + (src1[col] == src2[row]?1:0);
                dp[row][col] = temp;
            }
        }
        return dp[src2.length-1][src1.length-1];

    }

    private int process2(char[] src1,char[] src2){
        int[] dp = new int[src1.length];
        int topLeft  = 0;
        for (int i = 0; i < dp.length; i++) {
            dp[i] = (src1[i] == src2[0] ? 1:0);
        }

        for (int j = 1; j < src2.length; j++) {
            for (int i = 0; i < src1.length; i++) {
                if(i == 0){
                    topLeft = dp[0];
                    dp[i] = (src2[j] == src1[i] ? 1:0);
                }else {
                    int temp =  dp[i];
                    dp[i] = Math.max(topLeft,Math.max(dp[i-1],dp[i])) + (src2[j] == src1[i] ? 1:0);
                    topLeft = temp;
                }
            }
        }
        return dp[src1.length-1];

    }


}


public class HL5 {


    public static void main(String[] args) {
        //new Snake().test();
//        new Calculate().test();
        //System.out.println(new maxSameSeqStrLen().getLen("abcdefg", "acegdada"));
        System.out.println(new maxSameSubStrLen().getLen("abcdefg", "acedabcda"));

//        System.out.println(Integer.valueOf('+'));
//        System.out.println(Integer.valueOf('-'));
//        System.out.println(Integer.valueOf('*'));
//        System.out.println(Integer.valueOf('/'));
    }







}
